package myDoubleQueue;

import mySingleQueue.MyQueue;
import myStack.EmptyException;

//原理：先进先出
//思路：双向链表头尾无所谓，下面采用[头插、尾删]代替[入队、出队]
public class DQueue {
    // 定义双向链表节点
    static class Node {
        public int val;
        public Node prev;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    // 头结点
    public Node head;
    // 尾结点
    public Node last;
    // 队列长度
    public int size;

    //1.入队列：boolean offer(E e) 【头插】
    public boolean offer(int e) {
        Node node = new Node(e);
        // 判空
        if (isEmpty()) {
            head = node;
            last = node;
        } else {
            // 头插
            node.next = head;
            head.prev = node;
            head = head.prev;
        }
        size++;
        return true;
    }

    //2.出队列：E poll() 【尾删】
    public int poll() {
        // 判空
        if (isEmpty()) {
            // 这里可以自定义异常
            throw new EmptyException("队列为空!");
        }
        // 接收出队元素
        int ret = head.val;
        // 如果只有1个结点
        if (head.next == null) {
            last = null;
            head = null;
        } else {
            // 大于1个结点
            last.prev.next = null;
            last = last.prev;
        }
        size--;
        return ret;

    }

    //3.获取队头元素：int peek()
    public int peek() {
        // 判空
        if (isEmpty()) {
            // 这里可以自定义异常
            throw new EmptyException("队列为空!");
        }
        return head.val;
    }

    //4.获取队列中有效元素个数：int size()
    public int getSize() {
        return size;
    }

    //5.检测队列是否为空：boolean isEmpty()
    public boolean isEmpty() {
        return size == 0;
    }
}
